package stack;

import java.util.Stack;

//最小栈问题,要在普通栈的基础上,提供获取最小元素的功能,并且时间复杂度为O(1)
//无论这个栈如何出栈入栈,都能拿到最小值,这个时候思路就是再多创建一个栈(最小栈),两个栈先同时入栈第一个元素
//后面正常栈入第二个元素时,最小栈进行比较,如果入的元素比最小栈前一个元素小,就入栈,否则就将最小栈的前一个元素
//再入一次栈,后面这样一直操作,能够保证任何时候最小栈栈顶的元素都是当前栈的最小值
class MinStack {

    private Stack<Integer> stack1 = new Stack<>();

    private Stack<Integer> stack2 = new Stack<>();

    public MinStack(){
        //这个方法直接空着就可以

    }

    public void push(int val){
        //stack1就是正常入栈
        stack1.push(val);
        if(stack2.isEmpty()){
            stack2.push(val);
            return;
        }
        int min = stack2.peek();
        if(val < min){
            stack2.push(val);
        }else{
            stack2.push(min);
        }
    }

    public void pop(){
        //正常的取栈顶元素
        if(stack1.isEmpty()){
            return;//注:在解OJ题时,不要抛出异常,这样可能提交时会报错
        }
        //把这两个栈的元素都出栈
        stack1.pop();
        stack2.pop();
    }

    public int top(){
        if(stack1.isEmpty()){
            return 0;
        }
        return stack1.peek();
    }

    public int getMin(){
        if(stack2.isEmpty()){
            return 0;
        }
        return stack2.peek();

    }

}
